#include<vector>
#include<deque>
using namespace std;

//双指针
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        if(k<=1)return nums;
        vector<int> res(len-k+1, 0);
        for (int i = 0; i < len-k+1; i++)
        {
            int left = i;
            int right = left+k-1;
            int tmp = nums[left];
            for ( int j = left; j <= right; j++)
            {
                if (nums[j]>tmp){
                    tmp = nums[j];
                }
            }
            res[i] = tmp;
        }
        return res;
    }
    //双端队列
    vector<int> maxSlidingWindow1(vector<int>& nums, int k) {
        int n = nums.size() ;
        deque<int> dq ;
        vector<int> res ;

        if (nums.size() == 0)
            return res ;
    
        for (int i = 0 ; i < n ; ++i) {
            while (!dq.empty() && i - dq.front() + 1 > k) {
                dq.pop_front() ;
            }
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back() ;
            }
            dq.push_back(i) ;
            if (i >= k - 1)
                res.push_back(nums[dq.front()]) ;
        }
        return res ;
    }
};